package 买卖股票的最佳时机III;

import java.util.Arrays;

/**
 * @author: AirMan
 * @date: 2025/5/14 13:19
 * @description:
 */
public class Solution2 {
    public int maxProfit(int[] prices) {
        // 对方法一的空间优化
        // ① dp数组及其下标含义：dp[i][j]表示第i天状态位j的最大金额
        //                    状态一共有四个，第一次持有股票(状态0)，第一次卖出股票(1)，第二次持有股票(2)，第二次卖出股票(3)
        // ② 状态转移方程：dp[i][0] = Math.max(-prices[i], dp[i-1][0]);
        //               dp[i][1] = Math.max(dp[i-1][0] + prices[i], dp[i-1][1]);
        //               dp[i][2] = Math.max(dp[i-1][1] - prices[i], dp[i-1][2]);
        //               dp[i][3] = Math.max(dp[i-1][2] + prices[i], dp[i-1][3]);
        // ③ dp数组的初始化：dp[0][0] = -prices[0], dp[0][1] = 0, dp[0][2] = -prices[0], dp[0][3] = 0;
        int[][] dp = new int[2][4];
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        dp[0][2] = -prices[0];
        dp[0][3] = 0;
        for (int i = 1; i < prices.length; i++) {
            // 更新当天的状态
            dp[1][0] = Math.max(-prices[i], dp[0][0]);
            dp[1][1] = Math.max(dp[0][0] + prices[i], dp[0][1]);
            dp[1][2] = Math.max(dp[0][1] - prices[i], dp[0][2]);
            dp[1][3] = Math.max(dp[0][2] + prices[i], dp[0][3]);
            // 更新当前状态为前一天的状态
            dp[0][0] = dp[1][0];
            dp[0][1] = dp[1][1];
            dp[0][2] = dp[1][2];
            dp[0][3] = dp[1][3];
        }
        print(dp);
        return dp[1][3];
    }

    private void print(int[][] dp) {
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[0].length; j++) {
                System.out.print(Arrays.toString(dp[i]) + "\t");
            }
            System.out.println();
        }
    }
}
